#include "hw5.h"

/*****核心功能函数（递归）*****/
int smallcount(int k, btree root)
{
    if (root == nullptr)
    {
        return 0;
    }
    else if (IsBST(root) == false) //本题的函数只可以用于BST！
    {
        return -1;
    }
    else
    {
        int count;
        count = smallcount(k, root->lc); //根节点左子树中符合要求的个数
        if (root->data <= k)
        {
            count = count + 1;
            if (root->data == k) //结点值刚好等于K，直接返回count
            {
                return count;
            }
        }
        else
        {
            return count;
        }
        count = count + smallcount(k, root->rc);
        return count;
    }
}
/*****核心功能函数*****/

/*****主函数中输出结果*****/
void main_print(btree root)
{
    print_t(root);
    printf("\n");
    for (int k = 1; k <= 11; k++)
    {
        int count = smallcount(k, root);
        if (count < 0)
        {
            printf("不是BST!\n");
            break;
        }
        else
        {
            if (k < 10)
            {
                printf("该BST中值不大于 %d的结点个数：%d\n", k, count);
            }
            else
            {
                printf("该BST中值不大于%d的结点个数：%d\n", k, count);
            }
        }
    }
}
/*****主函数中输出结果*****/

/*****主函数*****/
int main()
{
    printf("递归\n\n\n\n");
    
    t0 = NULL;
    t1 = (btree)malloc(sizeof(btnode));
    t2 = (btree)malloc(sizeof(btnode));
    t3 = (btree)malloc(sizeof(btnode));
    t4 = (btree)malloc(sizeof(btnode));
    t5 = (btree)malloc(sizeof(btnode));
    t6 = (btree)malloc(sizeof(btnode));
    t7 = (btree)malloc(sizeof(btnode));
    t8 = (btree)malloc(sizeof(btnode));
    t9 = (btree)malloc(sizeof(btnode));

    btree root;

    /***空二叉树***/
    printf("*****空二叉树*****\n");
    t_init();
    root = t0;
    main_print(root);
    printf("*****空二叉树*****\n\n\n\n");
    /***空二叉树***/

    /***第1棵非空二叉树***/
    printf("/*****第1棵非空二叉树*****/\n");
    t_init();
    t1->lc = t2;
    t1->rc = t3;
    t2->lc = t4;
    t2->rc = t5;
    t3->lc = t6;
    t3->rc = t7;
    root = t1;
    main_print(root);
    printf("/*****第1棵非空二叉树*****/\n\n\n\n");
    /***第1棵非空二叉树***/

    /***第2棵非空二叉树***/
    printf("/*****第2棵非空二叉树*****/\n");
    t_init();
    t5->lc = t3;
    t3->lc = t2;
    t5->rc = t7;
    t7->lc = t6;
    t7->rc = t9;
    t9->lc = t8;
    root = t5;
    main_print(root);
    printf("/*****第2棵非空二叉树*****/\n\n\n\n");
    /***第2棵非空二叉树***/

    /***第3棵非空二叉树***/
    printf("/*****第3棵非空二叉树*****/\n");
    t_init();
    t5->lc = t3;
    t3->lc = t2;
    t3->rc = t4;
    t2->lc = t1;
    t5->rc = t7;
    t7->lc = t6;
    t7->rc = t9;
    t9->lc = t8;
    root = t5;
    main_print(root);
    printf("/*****第3棵非空二叉树*****/\n\n\n\n");
    /***第3棵非空二叉树***/

    /***第4棵非空二叉树***/
    printf("/*****第4棵非空二叉树*****/\n");
    t_init();
    root = t5;
    main_print(root);
    printf("/*****第4棵非空二叉树*****/\n\n\n\n");
    /***第4棵非空二叉树***/

    system("pause");
}